﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 链表
{
    class Program
    {
        static void Main(string[] args)
        {
            //LinkedList<Polynomial> fir = new LinkedList<Polynomial>();
            ////LinkedList<Polynomial> sec = new LinkedList<Polynomial>();
            //fir.Add(new Polynomial(1000, 5));
            //fir.Add(new Polynomial(2000, 5));
            //fir.Add(new Polynomial(3000, 5));
            //sec.Add(new Polynomial(1000, 50));
            //sec.Add(new Polynomial(1000, 50));
            //var result = PolyNomialMultiplication(fir, sec);
            //foreach (var i in fir)
            //{
            //    if (fir.Count() > 2)
            //        fir.Delete(2);
            //}
            int a = DigitValue(121, 100);
            int b = DigitValue(222, 1000);
            int c = DigitValue(121, 1);


        }
        /// <summary>
        /// 多项式乘法
        /// </summary>
        /// <param name="firstPolynomial"></param>
        /// <param name="secondPolynomial"></param>
        /// <returns></returns>
        static LinkedList<Polynomial> PolyNomialMultiplication(LinkedList<Polynomial> firstPolynomial, LinkedList<Polynomial> secondPolynomial)
        {

            if (firstPolynomial.IsNull)
            {
                return secondPolynomial;
            }
            if (secondPolynomial.IsNull)
                return firstPolynomial;
            LinkedList<Polynomial> temp = new LinkedList<Polynomial>();

            Polynomial tempPolynomial;

            foreach (var first in firstPolynomial)
            {
                foreach (var second in secondPolynomial)
                {
                    tempPolynomial = new Polynomial();
                    tempPolynomial.Coeff = second.Coeff * first.Coeff;
                    tempPolynomial.HightPower = first.HightPower + second.HightPower;
                    temp.Add(tempPolynomial);
                }
            }
            //合并多项式
            for (int i = 1; i <= temp.Count(); i++)
            {
                for (int j = i + 1; j <= temp.Count(); j++)
                {
                    if (temp[i].HightPower == temp[j].HightPower)
                    {
                        temp[i].Coeff += temp[j].Coeff;
                        temp.Delete(j);
                        j--;
                    }
                }
            }
            return temp;
        }
        /// <summary>
        /// 基数排序，值为int32
        /// </summary>
        /// <param name="arrOrginalSource"></param>
        /// <returns></returns>
        static LinkedList<IntValue> RadixSort(int[] arrOrginalSource)
        {
            //用数组储存10链表桶
            LinkedList<IntValue>[] buckets = new LinkedList<IntValue>[10];
            //用于要排序的次数
            int time;
            //临时容器用于存储
            LinkedList<IntValue> temp = new LinkedList<IntValue>();
            //第一次把数组里面的值根据个位上个数据 把他们分到指定buckets里面去,并求出数组最大值（用于确定排序的趟数）
            int value;
            int MaxarrOrginalSource = 0;
            for (int i = 0; i < arrOrginalSource.Count(); i++)
            {
                //求出最大值
                if (arrOrginalSource[i] > MaxarrOrginalSource)
                {
                    MaxarrOrginalSource = arrOrginalSource[i];
                }
                //获取个位数上的值
                value = DigitValue(arrOrginalSource[i], 1);
                buckets[value].Add(new IntValue(arrOrginalSource[i]));
            }

            for(int i=0;i<10;i++)
            {
                temp.AddRang(buckets[i]);
                buckets[i] = null;
            }        
            //求出最高位
            time = MaxarrOrginalSource.ToString().Count();
            //剩余趟数进行遍历
            for (int n = 1; n < time; n++)
            {
                foreach(var a in temp)
                {
                    value = DigitValue(a.Value, (int)Math.Pow(10, n));
                    buckets[value].Add(a);
                }

                for (int i = 0; i < 10; i++)
                {
                    temp.AddRang(buckets[i]);
                    buckets[i] = null;
                }
            }
            return temp;
        }

        /// <summary>
        /// 计算指定位数上的值
        /// </summary>
        /// <param name="source">要计算的值</param>
        /// <param name="digit">指定的位数</param>
        /// <returns></returns>
        static int DigitValue(int source, int digit)
        {
            return (source % (digit * 10)) / digit;

        }


     




    }

    /// <summary>
    /// 多项式项
    /// </summary>
    public class Polynomial
    {

        public Polynomial()
        { }
        public Polynomial(int hightPowe, int coeff)
        {
            HightPower = hightPowe;
            Coeff = coeff;

        }
        /// <summary>
        /// 幂数
        /// </summary>
        public int HightPower { get; set; }
        /// <summary>
        /// 系数
        /// </summary>
        public int Coeff { get; set; }
    }

    /// <summary>
    /// 封装排序用的int，好使用自己的链表类
    /// </summary>
    public class IntValue
    {
        public IntValue(int n)
        {
            Value = n;

        }
        public int Value { get; set; }
        public override string ToString()
        {
            return Value.ToString();
        }
    }




}
